package com.leetcode.algorithm.y18.m05;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import com.leetcode.algorithm.common.ListNode;

/**
 * leetcode-cn.com
 * 70. 爬楼梯
 * 83. 删除排序链表中的重复元素
 * 88. 合并两个有序数组
 * 118. 杨辉三角
 * 119.杨辉三角 II
 * @author dengjie213@126.com
 * 2018年5月7日 下午10:54:42
 */
public class MySolution0507 {

	/**
	 * 70. 爬楼梯 
	 * 假设你正在爬楼梯。需要 n 步你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 
	 * 注意：给定 n 是一个正整数。
	 * 
	 * 示例 1： 输入： 2 输出： 2 
	 * 解释： 有两种方法可以爬到楼顶。 
	 * 1. 1 步 + 1 步 
	 * 2. 2 步
	 * 
	 * 示例 2： 
	 * 输入： 3 
	 * 输出： 3 
	 * 解释： 有三种方法可以爬到楼顶。 
	 * 1. 1 步 + 1 步 + 1 步 
	 * 2. 1 步 + 2 步 
	 * 3. 2 步 + 1 步
	 * 
	 * @param n
	 * @return
	 */
	public int climbStairs(int n) {
		if (n == 0 || n == 1) {
			return 1;
		}
		if (n == 2) {
			return 2;
		}
		// return climbStairs(n - 1) + climbStairs(n - 2);
		int pre = 1; // 对应n=1
		int cur = 2; // 对应n=2
		int i = 3;
		while (i < n) {
			int tmp = pre;
			pre = cur;
			cur += tmp;
			i++;
		}
		return pre + cur;
	}
	
	// 用数组
	public int climbStairsBetter(int n) {
		if (n == 0 || n == 1) {
			return 1;
		}
		if (n == 2) {
			return 2;
		}
		// return climbStairs(n - 1) + climbStairs(n - 2);
		int[] ret = new int[n];	
		ret[0] = 1;
		ret[1] = 2;
		for (int i = 2; i < n; i++) {
			ret[i] = ret[i-1] + ret[i-2];
		}
		return ret[n-1];
	}
	
	/**
	 * 83. 删除排序链表中的重复元素 
	 * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
	 * 
	 * 示例 1:
	 * 输入: 1->1->2 
	 * 输出: 1->2 
	 * 
	 * 示例 2:
	 * 输入: 1->1->2->3->3 
	 * 输出: 1->2->3
	 * 
	 * @param head
	 * @return
	 */
	public ListNode deleteDuplicates(ListNode head) {
		if (head == null) {
			return head;
		}
		ListNode preNode = head;
		ListNode curNode = head.next;
		while (curNode != null) {
			if (curNode.val != preNode.val) {
				preNode = curNode;
				curNode = curNode.next;
			}else {
				// 删除链表中的元素
				curNode = curNode.next;
				preNode.next = curNode;
			}
		}
		return head;
	}

	/**
	 * 88. 合并两个有序数组 
	 * 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
	 * 
	 * 说明:
	 * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 
	 * 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 
	 * 
	 * 示例:
	 * 输入: nums1 = [1,2,3,0,0,0], m = 3; nums2 = [2,5,6], n = 3
	 * 输出: [1,2,2,3,5,6]
	 * 
	 * @param nums1
	 * @param m
	 * @param nums2
	 * @param n
	 */
	public void merge(int[] nums1, int m, int[] nums2, int n) {
		if (n == 0) {
			return;
		}
		if (m == 0) {
			for (int i = 0; i < n; i++) {
				nums1[i] = nums2[i];
			}
			return ;
		}

		boolean asc = true;
		int cur1Idx = m - 1;
		int cur1EndIdx = -1;
		if (nums1[0] > nums1[m - 1]) {
			asc = false;
		}
		boolean idxAsc = true;
		int cur2Idx = 0;
		int cur2EndIdx = n;
		if ((nums2[0] >= nums2[n - 1]) == (nums1[0] > nums1[m - 1])) {
			idxAsc = false;
			cur2Idx = n - 1;
			cur2EndIdx = -1;
		}

		for (int i = m + n - 1; i >= 0; i--) {
			if (cur1Idx != cur1EndIdx && cur2Idx != cur2EndIdx) {
				if (asc) {
					if (nums1[cur1Idx] > nums2[cur2Idx]) {
						nums1[i] = nums1[cur1Idx--];
					} else {
						nums1[i] = nums2[cur2Idx];
						if (idxAsc) {
							cur2Idx++;
						} else {
							cur2Idx--;
						}
					}
				} else {
					if (nums1[cur1Idx] >= nums2[cur2Idx]) {
						nums1[i] = nums2[cur2Idx];
						if (idxAsc) {
							cur2Idx++;
						} else {
							cur2Idx--;
						}
					} else {
						nums1[i] = nums1[cur1Idx--];
					}
				}
			} else {
				if (cur2Idx == cur2EndIdx) {
					break;
				} else if (cur1Idx == cur1EndIdx) {
					while (cur2Idx != cur2EndIdx) {
						nums1[i] = nums2[cur2Idx];
						if (idxAsc) {
							cur2Idx++;
						} else {
							cur2Idx--;
						}
						i--;
					}
					break;
				}
			}
		}

	}
	
	public void mergeAsc(int[] nums1, int m, int[] nums2, int n) {
		// 假设nums1和nums2都是升序
		if (n == 0) {
			return;
		}
		if (m == 0) {
			for (int i = 0; i < n; i++) {
				nums1[i] = nums2[i];
			}
		}
		int cur1Idx = 0;
		int cur2Idx = 0;
		while (cur1Idx < m || cur2Idx < n) {
			int i = cur1Idx;
			while (i < m && nums2[cur2Idx] >= nums1[i]) {
				i++;
			}
			cur1Idx = i;
			if (i == m) {
				// 将nums2 [cur2Idx,n-1]加入到nums1
				for (int j = cur2Idx; j < n; j++) {
					nums1[cur1Idx + (j-cur2Idx)] = nums2[j];
				}
				break;
			} else {
				// nums2[cur2Idx] > nums1[i],需要将nums2部分元素合并到nums1
				i = cur2Idx;
				while (i < n && nums2[i] <= nums1[cur1Idx]) {
					i++;
				}
				int size = i - cur2Idx;
				m += size;
				// 将nums1[cur1Idx]开始的size个元素整体后移,将nums2[cur2Idx]开始的size个元素加入到nums1[cur1Idx...]
				// 将nums1[cur1Idx]开始的size个元素整体后移size个位置
				for (int j = 1; j <= size; j++) {
					nums1[m - j] = nums1[m - j - size];// 从最后一个，倒数第二个依次赋值
				}
				// 将nums2[cur2Idx]开始的size个元素加入到nums1[cur1Idx...]
				for (int j = 0; j < size; j++) {
					nums1[cur1Idx + j] = nums2[cur2Idx + j];
				}
				cur1Idx += size;
				cur2Idx += size;
			}
		}
		
	}
    
    /**
     * 118. 杨辉三角
     * 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
     * 在杨辉三角中，每个数是它左上方和右上方的数的和。
	 *	示例:
	 *	输入: 5
	 *	输出:
	 *	[
	 *	     [1],
	 *	    [1,1],
	 *	   [1,2,1],
	 *	  [1,3,3,1],
	 *	 [1,4,6,4,1]
	 *	]
     * @param numRows
     * @return
     */
	public List<List<Integer>> generate(int numRows) {
		List<List<Integer>> ret = new ArrayList<List<Integer>>();
		Integer[] l0 = new Integer[] {};
		List<Integer> cur = null;
		for (int i = 1; i <= numRows; i++) {
			List<Integer> list = Arrays.asList(Arrays.copyOf(l0, i));
			for (int j = 0; j < i; j++) {
				if (j == 0 || j == i - 1) {
					list.set(j, 1);
				} else {
					list.set(j, cur.get(j - 1) + cur.get(j));
				}
			}
			cur = list;
			ret.add(cur);
		}
		return ret;
	}
    
	/**
	 * 119.杨辉三角 II 
	 * 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 
	 * 在杨辉三角中，每个数是它左上方和右上方的数的和。
	 * 
	 * 示例:
	 * 输入: 3 
	 * 输出: [1,3,3,1] 
	 * 
	 * 进阶：
	 * 你可以优化你的算法到 O(k) 空间复杂度吗？
	 * 
	 * @param rowIndex
	 * @return
	 */
    public List<Integer> getRow(int rowIndex) {
    	rowIndex++;
		if (rowIndex == 0) {
			return Arrays.asList();
		}
		Integer[] list0 = new Integer[] {};
		List<Integer> cur = null;
		for (int i = 1; i <= rowIndex; i++) {
			List<Integer> list = Arrays.asList(Arrays.copyOf(list0, i));
			for (int j = 0; j < i; j++) {
				if (j == 0 || j == i - 1) {
					list.set(j, 1);
				} else {
					list.set(j, cur.get(j - 1) + cur.get(j));
				}
			}
			cur = list;
		}
		return cur;
	}
}
